# Dear GAP-forum,
#
# the PermGroupOps.Normalizer function of gap3r4p1 may be
# improved to handle cyclic groups of low degree more efficiently.
# Maybe this has already been done in a later releases?
#
# Sebastian Egner.

# Lemma:
#   Let u in G be of order r then the normalizer of <u> in G is
#
#     N(G, <u>) =
#       DisjointUnion(
#         C(G, u)*x[k] :
#           1 <= k < r and gcd(k, r) = 1 and
#           the equation u^x = u^k has a solution x[k] in G
#       )
#
#   where C(G, u) denotes the centralizer of u in G.
#
# Proof (elementary, easy):
#   1. Consider c in C(u) so u^c = u. Then calculate
#      u^(c*x[k]) = (u^c)^x[k] = u^x[k] = u^k ==> c*x[k] in N(<u>).
#   2. Conversely consider x in N(<u>). Then u^x = u^k for some
#      k in {0, .., r-1} and ord(u^k) = ord(u^x) = ord(u) = r implies
#      gcd(k, r) = 1. In addition u^x[k] = u^k = u^x implies
#      u = u^(x*x[k]^-1) and hence x*x[k]^-1 in C(u) or equivalently
#      x in C(u)*x[k]. q.e.d.

# Comments:
#   * The equation a^x = b can be solved quickly using a BSGS.
#   * Centralizers are much faster to compute than Normalizers.
#   * There are Phi(r) many equations to be solved.
#   * Let n be the number of points moved by u. Define rmax(n)
#     to be the maximal order of a permutation on n points. Observe
#        rmax(  1) = 1
#        rmax(  2) = 2
#        rmax(  3) = 3
#        rmax(  4) = 3
#        rmax(  5) = 6
#        rmax(  6) = 6
#        rmax(  7) = 7
#        rmax(  8) = 15
#        rmax(  9) = 15
#        rmax( 10) = 30
#        rmax( 12) = 42
#        rmax( 14) = 42
#        rmax( 16) = 105
#        rmax( 18) = 210
#        rmax( 20) = 210
#        rmax( 30) = 2730 ; no *not* use the proposed function
#        rmax( 40) = 15015
#        rmax( 50) = 51870
#        rmax( 60) = 570570
#        rmax( 70) = 1385670
#        rmax( 80) = 9699690
#        rmax( 90) = 20281170
#        rmax(100) = 223092870
#     So the bottom line is:
#       * If rmax(n) <= 20 then always use the conjugation method.
#       * Otherwise compute Phi( OrderPerm( u ) ) and use other
#         methods if this exceeds some bound (say 200).
#       * The computation of Phi can often be avoided by using a
#         lower bound on Phi which comes down
#         to Phi(r) > 200 for r > 1000.

# NormalizerCyclePermGroup( <permgroup>, <cyclic-subgroup> )
# computes the normalizer of the subgroup in the permgroup.

NormalizerCyclicPermGroup := function ( G, U )
  local u, # generator of U
        r, # order of u
        k, # counter for the k with gcd(k, r) = 1
        T, # transversal of N(G, U)/C(G, u)
        t; # element of T

# get generator of U and its order
u := U.generators[1];
r := OrderPerm(u);
if r = 1 then
  return G;
fi;

# decide on the method
if r > 1000 or Phi(r) > 200 then
  return Normalizer(G, U); # good luck!
fi;

# compute transversal of N(G, U)/C(G, u)
T := [];
for k in PrimeResidues(r) do
  t := RepresentativeOperation(G, u, u^k);
  if t <> false then
    Add(T, t);
  fi;
od;

  # N(G, U) = < C(G, u) union T > by the lemma
  Append(T, Centralizer(G, u).generators);
  return Subgroup(G, T);
end;

# A simple example:
#   G  := SymmetricGroup(10);
#   U  := Subgroup(G, [( 1, 3, 8, 6, 5, 7, 2,10, 4)]);
#   N1 := NormalizerCyclicPermGroup(G, U); time;
#   --> 1980   (2 seconds)
#   N2 := Normalizer(G, U); time;
#   --> 105540 (1.5 minutes)